package kg.aibek.projecteuler.p51;

public class Problem66 {
	public void solve() {
		long a[] = new long[1000000];

		for (int i = 0; i < a.length; i++) {
			a[i] = (long) i * i;
		}

		boolean b[] = new boolean[10000];
		long res[] = new long[10000];

		int setCount = 100;

		outer: for (int i = 1; i < a.length; i++) {
			if (setCount >= 10000)
				break;

			for (int j = i + 1; j < a.length; j++) {
				long l = a[j] / a[i];
				if (l > 10000) {
					continue outer;
				}

				long ll = a[j] - l * a[i];
				if (ll == 1 && !b[(int) l]) {
					setCount++;
					b[(int) l] = true;
					res[(int) l] = j;
				}
				ll = a[j] - (l - 1) * a[i];
				if (ll == 1 && !b[(int) l - 1]) {
					setCount++;
					b[(int) l - 1] = true;
					res[(int) l - 1] = j;
				}
				ll = a[j] - (l + 1) * a[i];
				if (ll == 1 && !b[(int) l + 1]) {
					setCount++;
					b[(int) l + 1] = true;
					if (l + 1 < 10000) {
						res[(int) l + 1] = j;
					}
				}
			}
		}
		long max = res[0];
		for (int i = 1; i < res.length; i++) {
			if (max < res[i]) {
				max = res[i];
			}
		}

		System.out.println(max);
	}

	public static void main(String[] args) {
		Problem66 p = new Problem66();
		p.solve();
	}
}
